// 插入排序
// 获取第二个数据和第一个数据进行比较，如果二小就和一交换位置，这样一二就做到了有序，然后第三个在和第二个做比较如果三小就让三和二交换位置，然后在让第三个和第一个做比较依次类推，我们可以发现插入排序和数据有关系，在最差的
// 情况下插入排序的时间复杂度是O(N^2)最好的情况下插入排序的时间复杂度是O(N)
const insertionSort = (arr:number[]) => {
    if( arr == null || arr.length < 2 ) return
    for(let i = 0; i < arr.length; i++){
        for(let j = i-1; j >=0 && arr[j] > arr[j+1]; j--){
            swap(arr,j,j+1)
        }
    }
}
const swap = function (arr: number[],j,i){
    arr[i] = arr[j] ^ arr[i]
    arr[j] = arr[j] ^ arr[i]
    arr[i] = arr[j] ^ arr[i]
}
export default insertionSort